home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / tests / tMap.cc < prev    next >
C/C++ Source or Header  |  1993-06-06  |  7KB  |  334 lines
  1. /*
  2.  a test file for Maps
  3. */
  4.  
  5. #ifdef PTIMES
  6. const int ptimes = 1;
  7. #else
  8. const int ptimes = 0;
  9. #endif
  10.  
  11. #include <stream.h>
  12. #include <assert.h>
  13. #include <builtin.h>
  14.  
  15.  
  16. #define tassert(ex) { cerr << #ex; \
  17.                        if ((ex)) cerr << " OK\n"; \
  18.                        else cerr << " Fail\n"; }
  19.  
  20. #include "iMap.h"
  21.  
  22. unsigned int hash(int x) { return multiplicativehash(x) ; }
  23.  
  24. int SIZE;
  25.  
  26. int *nums;
  27. int *odds;
  28. int *perm;
  29.  
  30. void add(int x[], int y[], intintMap& a)
  31. {
  32.   for (int i = 0; i < SIZE; ++i) a[x[i]] = y[i];
  33. }
  34.  
  35. #include <MLCG.h>
  36.  
  37. MLCG randgen;
  38.  
  39. void permute(int x[])
  40. {
  41.   for (int i = 1; i < SIZE; ++i)
  42.   {
  43.     int j = randgen.asLong() % (i + 1);
  44.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  45.   }
  46. }
  47.  
  48. void makenums()
  49. {
  50.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
  51. }
  52.  
  53. void makeodds()
  54. {
  55.   for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  56.   permute(odds);
  57. }
  58.  
  59. void makeperm()
  60. {
  61.   for (int i = 0; i < SIZE; ++i) perm[i] = i + 1;
  62.   permute(perm);
  63. }
  64.  
  65. void printMap(intintMap& a)
  66. {
  67.   int maxprint = 20;
  68.   cout << "[";
  69.   int k = 0;
  70.   for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
  71.     cout << "(" << a.key(i) << ", " <<  a.contents(i) << ") ";
  72.   if (i != 0) cout << "...]\n";
  73.   else cout << "]\n";
  74. }
  75.  
  76. #include "iSplayMap.h"
  77.  
  78. void Splaytest()
  79. {
  80.   intintSplayMap a(-1);
  81.   add(nums, perm, a);
  82.   intintSplayMap b(-1);
  83.   add(perm, nums, b);
  84.   intintSplayMap c(-1);
  85.   add(perm, odds, c); 
  86.   intintSplayMap d(a);
  87.   add(nums, nums, d);
  88.   cout << "a: "; printMap(a);
  89.   cout << "b: "; printMap(b);
  90.   cout << "c: "; printMap(c);
  91.   cout << "d: "; printMap(d);
  92.   assert(a.length() == SIZE);
  93.   assert(b.length() == SIZE);
  94.   assert(c.length() == SIZE);
  95.   assert(d.length() == SIZE);
  96.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  97.   assert(a[SIZE+1] = -1);
  98.  
  99.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  100.  
  101.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  102.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  103.  
  104.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  105.  
  106.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  107.  
  108.   d.del(1);
  109.   assert(!d.contains(1));
  110.   for (j = 1; j <= SIZE; ++j) d.del(j);
  111.   assert(d.empty());
  112.  
  113.   assert(a.OK());
  114.   assert(b.OK());
  115.   assert(c.OK());
  116.   assert(d.OK());
  117.  
  118. }
  119.  
  120. #include "iVHMap.h"
  121.  
  122. void VHtest()
  123. {
  124.   intintVHMap a(-1, SIZE);
  125.   add(nums, perm, a);
  126.   intintVHMap b(-1, SIZE);
  127.   add(perm, nums, b);
  128.   intintVHMap c(-1, SIZE);
  129.   add(perm, odds, c); 
  130.   intintVHMap d(a);
  131.   add(nums, nums, d);
  132.   cout << "a: "; printMap(a);
  133.   cout << "b: "; printMap(b);
  134.   cout << "c: "; printMap(c);
  135.   cout << "d: "; printMap(d);
  136.   assert(a.length() == SIZE);
  137.   assert(b.length() == SIZE);
  138.   assert(c.length() == SIZE);
  139.   assert(d.length() == SIZE);
  140.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  141.   assert(a[SIZE+1] = -1);
  142.  
  143.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  144.  
  145.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  146.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  147.  
  148.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  149.  
  150.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  151.  
  152.   d.del(1);
  153.   assert(!d.contains(1));
  154.   for (j = 1; j <= SIZE; ++j) d.del(j);
  155.   assert(d.empty());
  156.  
  157.   assert(a.OK());
  158.   assert(b.OK());
  159.   assert(c.OK());
  160.   assert(d.OK());
  161.  
  162. }
  163.  
  164. #include "iCHMap.h"
  165.  
  166. void CHtest()
  167. {
  168.   intintCHMap a(-1, SIZE);
  169.   add(nums, perm, a);
  170.   intintCHMap b(-1, SIZE);
  171.   add(perm, nums, b);
  172.   intintCHMap c(-1, SIZE);
  173.   add(perm, odds, c); 
  174.   intintCHMap d(a);
  175.   add(nums, nums, d);
  176.   cout << "a: "; printMap(a);
  177.   cout << "b: "; printMap(b);
  178.   cout << "c: "; printMap(c);
  179.   cout << "d: "; printMap(d);
  180.   assert(a.length() == SIZE);
  181.   assert(b.length() == SIZE);
  182.   assert(c.length() == SIZE);
  183.   assert(d.length() == SIZE);
  184.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  185.   assert(a[SIZE+1] = -1);
  186.  
  187.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  188.  
  189.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  190.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  191.  
  192.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  193.  
  194.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  195.  
  196.   d.del(1);
  197.   assert(!d.contains(1));
  198.   for (j = 1; j <= SIZE; ++j) d.del(j);
  199.   assert(d.empty());
  200.  
  201.   assert(a.OK());
  202.   assert(b.OK());
  203.   assert(c.OK());
  204.   assert(d.OK());
  205.  
  206. }
  207.  
  208. #include "iAVLMap.h"
  209.  
  210. void AVLtest()
  211. {
  212.   intintAVLMap a(-1);
  213.   add(nums, perm, a);
  214.   intintAVLMap b(-1);
  215.   add(perm, nums, b);
  216.   intintAVLMap c(-1);
  217.   add(perm, odds, c); 
  218.   intintAVLMap d(a);
  219.   add(nums, nums, d);
  220.   cout << "a: "; printMap(a);
  221.   cout << "b: "; printMap(b);
  222.   cout << "c: "; printMap(c);
  223.   cout << "d: "; printMap(d);
  224.   assert(a.length() == SIZE);
  225.   assert(b.length() == SIZE);
  226.   assert(c.length() == SIZE);
  227.   assert(d.length() == SIZE);
  228.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  229.   assert(a[SIZE+1] = -1);
  230.  
  231.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  232.  
  233.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  234.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  235.  
  236.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  237.  
  238.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  239.  
  240.   d.del(1);
  241.   assert(!d.contains(1));
  242.   for (j = 1; j <= SIZE; ++j) d.del(j);
  243.   assert(d.empty());
  244.  
  245.   assert(a.OK());
  246.   assert(b.OK());
  247.   assert(c.OK());
  248.   assert(d.OK());
  249.  
  250. }
  251.  
  252. #include "iRAVLMap.h"
  253.  
  254. void RAVLtest()
  255. {
  256.   intintRAVLMap a(-1);
  257.   add(nums, perm, a);
  258.   intintRAVLMap b(-1);
  259.   add(perm, nums, b);
  260.   intintRAVLMap c(-1);
  261.   add(perm, odds, c); 
  262.   intintRAVLMap d(a);
  263.   add(nums, nums, d);
  264.   cout << "a: "; printMap(a);
  265.   cout << "b: "; printMap(b);
  266.   cout << "c: "; printMap(c);
  267.   cout << "d: "; printMap(d);
  268.   assert(a.length() == SIZE);
  269.   assert(b.length() == SIZE);
  270.   assert(c.length() == SIZE);
  271.   assert(d.length() == SIZE);
  272.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  273.   for (j = 1; j <= a.length(); ++j) assert(a.rankof(j) == j);
  274.   for (j = 1; j <= a.length(); ++j) assert(a.key(a.ranktoPix(j)) == j);
  275.   assert(a[SIZE+1] = -1);
  276.  
  277.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  278.  
  279.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  280.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  281.  
  282.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  283.  
  284.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  285.  
  286.   d.del(1);
  287.   assert(!d.contains(1));
  288.   for (j = 1; j <= SIZE; ++j) d.del(j);
  289.   assert(d.empty());
  290.  
  291.   assert(a.OK());
  292.   assert(b.OK());
  293.   assert(c.OK());
  294.   assert(d.OK());
  295.  
  296. }
  297.  
  298. double return_elapsed_time ( double );
  299. double start_timer ( );
  300.  
  301. int main(int argv, char** argc)
  302. {
  303.   if (argv > 1)
  304.   {
  305.     SIZE = abs(atoi(argc[1]));
  306.     SIZE &= ~1;
  307.   }
  308.   else
  309.     SIZE = 100;
  310.   nums = new int[SIZE];
  311.   odds = new int[SIZE];
  312.   perm = new int[SIZE];
  313.   makenums();
  314.   makeodds();
  315.   makeperm();
  316.   start_timer();
  317.   cout << "Splaytest\n"; Splaytest();
  318.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  319.   start_timer();
  320.   cout << "VHtest\n"; VHtest();
  321.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  322.   start_timer();
  323.   cout << "CHtest\n"; CHtest();
  324.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  325.   start_timer();
  326.   cout << "AVLtest\n"; AVLtest();
  327.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  328.   start_timer();
  329.   cout << "RAVLtest\n"; RAVLtest();
  330.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  331.  
  332.   return 0;
  333. }
  334.